分位数算法总结

背景

首先说下，分位数(quantile)的概念，也就是我们监控中常见的p99， 这里举一个例子

排序为rank=⌊ϕN⌋的元素，其中N为序列中元素的个数。考虑以下例子数据：

11 , 21 , 24 , 61 , 81 , 39 , 89 , 56 , 12 , 51

查询ϕ−quantile分位点所在数据前，需要对无序数据进行排序：

input:  11   21   24   61   81   39   89   56   12   51
sort:   11   12   21   24   39   51   56   61   81   89
rank:   1    2    3    4    5    6    7    8    9    10

排序后，我想查这批数据的中位数 也就是：0.5−quantile 对应 rank=5，值为39

现时场景下，我们一般用这个来统计比如一段时间的调用延迟的p99，而上述操作无论在时间还是空间上成本比较高，实际场景中肯定不是这么实现的。

后文将阐述近年来实际工业中使用的各种分位数算法.

随机算法

论文

实现案例:

dropwizard 的 metrics 库提供的随机算法

原理解释:

维护一个固定长度的sample buffer数组，写sample时，随机确定是否插入到当前sample buffer 数组。

当需要查询quantile时，则进行传统的排序，计算quantile

时间复杂度

写	O(1)
读	O(nlogn)

空间占用

固定大小，gc影响为0

缺点： 数据失真严重

确定性算法

静态分桶

实现案例
HdrHistogram

思路还是分桶，只不过不是一个数字一个桶，而是一个区间一个桶。

该区间的范围可以是线性增长，可指数增长。

通过牺牲一小部分精度，从而达到减小空间占用，并且数据大致准确的结果。

下图中，采样范围在 [1-15]的有991个，在 [16-31]的有2个...

	时间复杂度
写	O(1)
读	O(n)

空间占用
根据采样点的范围以及精度分桶，大小固定。gc影响为0

缺点

1. 统计范围有限，需要预先确定

q-digest

论文

代码实现:

addthis stream-lib的Qdigest实现

本质上还是静态分桶，只是用完全二叉树存储数据。

他的使用场景为为大数据分块计算 histogram 后，可对多个histogram 快速归并

数据格式如下图所示

上图中，这颗树总共能统计 1-8，8个数字。其中，有4个3，6个4，2个5-6, 2个 7-8 , 1个 1-8

它将数据压缩的的目标就是将 σ 个采样点 变成 k 组数据输出。下面是将简述压缩树的过程

是否可以进行压缩，以2个约束条件作为宗旨

1. count(v) <= n/k
2. count(v) + count(vp1) + count(vp2) > n/k

vp1 vp2 就是下图框起来的3个点

如何计算Quantile?

用图1做例子

首先，我们把树上每个节点根据其数进行bfs，并进行编号，并根据其编号的值的个数做成一个二维组 （编号，count）

可得到

{〈1,1〉,〈6,2〉,〈7,2〉,〈10,4〉,〈11,6〉}

每个节点可表达的数据不同，比如 c可表达[5, 6], g 可表达[1,8]

然后再根据每个二维组，可表达的最大范围进行正序排序

{〈10,4〉 [3],〈11,6〉 [4],〈6,2〉 [5-6],〈7,2〉 [7-8], 〈1,1〉 [1-8]}

最后就是 count x 请求的分位数，确定index的套路。

对于 p50 = 0.5*15 = 7.5

4 + 6 > 7.5

所以p50 是 <11.6> 也就是4

时间复杂度

写	O(1)
读	O(nlogn)

优点：树的特点决定了，对相同规格的树，merge操作成本很低，适合大数据map reduce 场景下的多颗树的合并作业

缺点：

1. 需要预分桶
2. 空间占用较多

动态分桶

GK 算法

论文

思路，还是分桶，只不过这个桶的大小是变化的，论文的话是根据一个区间段来划分的，这里简化下，本质还是根据现存的相邻sample之间的距离确定下个sample是不是放在一个新的独立的桶，具体如下图

优点：

1. 不需要预设定统计范围
2. 根据sample的量的范围，大部分情况下较静态分桶节省空间

缺点：

1. 写成本比静态分桶高，比起静态分桶是一个确定的空间，他的空间会不定期扩大。
2. 精度不可控。
   1. 假设 sample数据很均匀的平铺在总的数据范围内，则会导致采样的节点数过多，甚至不如静态分桶。
   2. 假设 部分节点的距离较大，则会导致精度降低。

时间复杂度

写	O(nlogn)
读	O(n)

注： 实现时，需要维护一个buffer，当buffer满时需要做排序，所以写的成本按照最慢的来算，就是nlogn

空间占用

空间太可控，由于有merge成本，会有一定的gc成本

CKMS算法

论文

GK算法的升级版本，prometheus 的summary 就用的该算法

它引入了一个可配置的错误率的概念，从而解决了GK 精度不可控问题。

GK 的桶的大小是根据 sample之间的距离delta 决定的，而 CKMS 在抉择是否开辟新桶，则是根据用户设置的错误率。

delta = 错误率 x 总体sample个数，并以此决定分桶的大小。

下图是一个数据合并的例子

可见，当错误率为0.1时，当size > 10 时，会对range <=1 的进行合并

优点：

1. 不需要预设定统计范围
2. 根据sample的量的范围，大部分情况下较静态分桶节省空间
3. 空间上 完全靠用户参数 错误率 决定，更可控。

缺点：

1. 写成本比静态分桶高

时间复杂度

写	O(nlogn)
读	O(n)

注： 同上，需要维护一个buffer，写时，大部分情况下都是O(1), 触发merge 时由于需要做排序，所以O(nlogn)

空间占用

空间太可控，由于有merge，并且空间不可控，所以会有一定的gc成本

素描法 (sketch)

t-digest

作者源码: https://github.com/tdunning/t-digest

t-digest算法，比动态分桶算法更准，但是资源又可控

作者对他的简介

https://mapr.com/blog/some-important-streaming-algorithms-you-should-know-about/

论文

简单描述:

1. 本质上，还是动态分桶，但有以下几个特点

   1. 桶的大小在一开始就固定，ckms 并不固定，这样实现可以直接用数组，这对gc友好

   2. 桶划分函数也更适合于计算分位数场景，众所周知我们更关心 p9999, p999 的精度，对p90, p50 的精度并不太在意。

      所以在划分桶的函数上对2边分桶分的更细，对中间划分的更粗

      

   3. 桶的大小随着采样个数的增加而增加。（不这样也就没法保证空间固定了） 桶大小 = f(n) x 当前采样个数

时间复杂度:

写	O(nlogn)
读	O(n)

注： 写时，大部分情况下都是O(1), 触发merge 时排序，导致 O(nlogn)

空间复杂度:

总空间占用较为固定，对gc影响较小。

压测

最终我们基于以下3种较为可靠的算法做压测，做一个横向比较。

我们的场景，一般用于统计接口的 p99 的耗时。允许几十ms的误差。一般统计的范围为 0 - 6000

由于 CKMS 和 t-digest 的实现并非线程安全，所以对其读写操作时都加了把锁。测试代码在此

这里直接给结果:

	w (ops/ms)	r (ops/ms)	gc影响	空间(byte)
ckms	0.182	3670790	4次	32440
hdrhistogram	6.546	43	0	3352
tdigest	8.733	177045	0	13600

从上述结果可见，tdigest 的读写性能相对来说是最好的，但是他的空间占用却很厉害。hdrhistogram 反倒是出乎意料的写性能比tdigest略逊一筹。

仔细看源码会发现tdigest 为了减少gc影响，内部使用了多个固定长度的double数组来实现，

也就是说，假如采样的范围足够大时，tdigest 才能凸显出优势，不然，内存占用有点多。

所以，最终，在我们的场景下，还是选择 hdrhistogram

reference

qdigest
http://www.mathcs.emory.edu/~cheung/Courses/584/Syllabus/08-Quantile/Greenwald2.html

GK
https://blog.csdn.net/matrix_zzl/article/details/78641264

t-digest
https://blog.bcmeng.com/post/tdigest.html